package leetcode_zh

import (
	"container/heap"
	"fmt"
	"math"
	"sort"
	"strconv"
)

/**
 * @Description: 剑指 Offer 07. 重建二叉树
 * @Keyword: 前序遍历和中序遍历 还原二叉树
 * @Author: kami
 * @Date: 2022/7/1 21:41
 **/
func buildTree07(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}
	root := &TreeNode{preorder[0], nil, nil}
	i := 0
	for ; i < len(inorder); i++ {
		if inorder[i] == preorder[0] {
			break
		}
	}
	root.Left = buildTree(preorder[1:len(inorder[:i])+1], inorder[:i])
	root.Right = buildTree(preorder[len(inorder[:i])+1:], inorder[i+1:])
	return root
}

/**
 * @Description: 剑指 Offer 14- I. 剪绳子  中等
 * @Keyword: 数论，使3的个数最多
 * @Author: kami
 * @Date: 2022/7/4 8:30
 **/
func cuttingRope(n int) int {
	if n == 1 || n == 2 {
		return 1
	}
	if n == 3 {
		return 2
	}

	var sum = 1
	for n > 4 {
		sum *= 3
		n -= 3
	}

	return sum * n
}

/**
 * @Description: 剑指 Offer 14- II. 剪绳子 II 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/4 8:47
 **/
func cuttingRope14(n int) int {
	if n == 1 || n == 2 {
		return 1
	}
	if n == 3 {
		return 2
	}

	var sum = 1
	for n > 4 {
		sum = sum * 3 % 1000000007
		n -= 3
	}

	return sum * n % 1000000007
}

/**
 * @Description: 剑指 Offer 26. 树的子结构 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/4 8:50
 **/
func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if B == nil || A == nil {
		return false
	}
	var isSubTreeDfs func(a, b *TreeNode) bool
	isSubTreeDfs = func(a, b *TreeNode) bool {
		if a == nil {
			return false
		}
		if a.Val == b.Val && isSubTree(a, b) {
			return true
		}
		return isSubTreeDfs(a.Left, b) || isSubTreeDfs(a.Right, b)
	}

	return isSubTreeDfs(A, B)
}

func isSubTree(A, B *TreeNode) bool {
	if B == nil {
		return true
	}
	if A == nil || A.Val != B.Val {
		return false
	}
	return isSubTree(A.Left, B.Left) && isSubTree(A.Right, B.Right)
}

/**
 * @Description: 剑指 Offer 20. 表示数值的字符串 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/4 9:51
 **/
func isNumber(s string) bool {
	start, end := 0, len(s)-1
	// trim head and tail
	for ; start <= end && s[start] == ' '; start++ {
	}
	for ; end >= start && s[end] == ' '; end-- {
	}

	if start > end {
		return false
	}

	// 判断读取到某字符之前是否出现过数字，小数点，E/e，+/-
	isNum, isDot, isExp, isSign := false, false, false, false
	// start to judge
	for ; start <= end; start++ {
		c := s[start]
		if c == '+' || c == '-' {
			if isNum || isDot || isSign {
				return false
			}
			isSign = true
		} else if c == 'e' || c == 'E' {
			if !isNum || isExp {
				return false
			}
			isExp = true
			isDot = false
			isSign = false
			isNum = false
		} else if c == '.' {
			if isDot || isExp {
				return false
			}
			isDot = true
		} else if c >= '0' && c <= '9' {
			isNum = true
		} else {
			return false
		}
	}

	start--
	return (s[start] <= '9' && s[start] >= '0') || (isNum && s[start] == '.')
}

/**
 * @Description: 剑指 Offer 64. 求1+2+…+n 中等
 * @Keyword: n*(n+1) / 2
 * @Author: kami
 * @Date: 2022/7/6 14:00
 **/
func sumNums(n int) int {
	ans := 0
	var sum func(int) bool
	sum = func(n int) bool {
		ans += n
		return n > 0 && sum(n-1)
	}
	sum(n)
	return ans
}

/**
 * @Description:剑指 Offer 16. 数值的整数次方 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/8 13:58
 **/
func myPow(x float64, n int) float64 {
	if n >= 0 {
		return quickMul(x, n)
	}
	return 1.0 / quickMul(x, -n)
}

func quickMul(x float64, n int) float64 {
	if n == 0 {
		return 1
	}
	y := quickMul(x, n/2)
	if n%2 == 0 {
		return y * y
	}
	return y * y * x
}

/**
 * @Description: 剑指 Offer 35. 复杂链表的复制 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/8 14:10
 **/
func copyRandomList(head *Node) *Node {
	var sourceCur = head
	// 索引：指向的索引，-1表示指向null
	var relateMap = make(map[*Node]*Node)
	for sourceCur != nil {
		relateMap[sourceCur] = &Node{
			Val: sourceCur.Val,
		}
		sourceCur = sourceCur.Next
	}
	sourceCur = head
	for sourceCur != nil {
		relateMap[sourceCur].Next = relateMap[sourceCur.Next]
		relateMap[sourceCur].Random = relateMap[sourceCur.Random]
		sourceCur = sourceCur.Next
	}

	return relateMap[head]
}

/**
 * @Description: 剑指 Offer 35. 复杂链表的复制 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/8 15:14
 **/
func copyRandomList1(head *Node) *Node {
	if head == nil {
		return nil
	}

	for node := head; node != nil; node = node.Next.Next {
		node.Next = &Node{Val: node.Val, Next: node.Next}
	}

	for node := head; node != nil; node = node.Next.Next {
		if node.Random != nil {
			node.Next.Random = node.Random.Next
		}
	}
	headNew := head.Next
	for node := head; node != nil; node = node.Next {
		nodeNew := node.Next
		node.Next = node.Next.Next
		if nodeNew.Next != nil {
			nodeNew.Next = nodeNew.Next.Next
		}
	}
	return headNew
}

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

/**
 * @Description: 剑指 Offer 31. 栈的压入、弹出序列 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/8 21:19
 **/
func validateStackSequences(pushed []int, popped []int) bool {
	var stack []int
	var size = len(pushed)
	var pushIdx int
	var popIdx int
	for pushIdx < size {
		stack = append(stack, pushed[pushIdx])
		for popIdx < size && len(stack) > 0 && stack[len(stack)-1] == popped[popIdx] {
			popIdx++
			stack = stack[:len(stack)-1]
		}
		pushIdx++
	}
	return len(stack) == 0
}

/**
 * @Description: 剑指 Offer 38. 字符串的排列 中等
 * @Keyword: 字符串全排列，使用回溯算法
 * @Author: kami
 * @Date: 2022/7/8 22:36
 **/
func permutation(s string) []string {
	var ans []string
	t := []byte(s)
	sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
	n := len(t)
	perm := make([]byte, 0, n)
	vis := make([]bool, n)
	var backtrack func(int)
	backtrack = func(i int) {
		if i == n {
			ans = append(ans, string(perm))
			return
		}
		for j, b := range vis {
			if b || j > 0 && !vis[j-1] && t[j-1] == t[j] {
				continue
			}
			vis[j] = true
			perm = append(perm, t[j])
			backtrack(i + 1)
			perm = perm[:len(perm)-1]
			vis[j] = false
		}
	}
	backtrack(0)
	return ans
}

/**
 * @Description: 剑指 Offer 32 - I. 从上到下打印二叉树 中等
 * @Keyword: 二叉树的层序遍历，栈
 * @Author: kami
 * @Date: 2022/7/10 13:54
 **/
func levelOrder321(root *TreeNode) []int {
	if root == nil {
		return []int{}
	}
	var res []int
	var stack = []*TreeNode{root}
	for len(stack) > 0 {
		var size = len(stack)
		var nextStack []*TreeNode
		for i := 0; i < size; i++ {
			res = append(res, stack[i].Val)
			if stack[i].Left != nil {
				nextStack = append(nextStack, stack[i].Left)
			}
			if stack[i].Right != nil {
				nextStack = append(nextStack, stack[i].Right)
			}
		}
		stack = nextStack
	}
	return res
}

/**
 * @Description: 剑指 Offer 44. 数字序列中某一位的数字 中等
 * @Keyword: 0123456789 10 11 12 13141516171819 20212223242526272829 303132…
 * @Author: kami
 * @Date: 2022/7/10 13:59
 **/
func findNthDigit(n int) int {
	digit, digitNum, count := 1, 1, 9
	for n > count {
		n -= count
		digit++
		digitNum *= 10
		count = 9 * digit * digitNum
	}
	num := digitNum + (n-1)/digit

	index := (n - 1) % digit

	numStr := strconv.Itoa(num)
	return int(numStr[index] - '0')
}

/**
 * @Description: 剑指 Offer 32 - III. 从上到下打印二叉树 III
 * @Keyword: 层序遍历，栈
 * @Author: kami
 * @Date: 2022/7/10 16:32
 **/
func levelOrder322(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	var res [][]int
	var stack = []*TreeNode{root}
	var pos = true
	for len(stack) > 0 {
		var size = len(stack)
		var nextStack []*TreeNode
		var curRes []int
		for i := 0; i < size; i++ {
			if stack[i].Left != nil {
				nextStack = append(nextStack, stack[i].Left)
			}
			if stack[i].Right != nil {
				nextStack = append(nextStack, stack[i].Right)
			}
			if pos {
				curRes = append(curRes, stack[i].Val)
			} else {
				curRes = append(curRes, stack[size-i-1].Val)
			}
		}
		stack = nextStack
		res = append(res, curRes)
		pos = !pos
	}
	return res
}

/**
 * @Description: 剑指 Offer 56 - I. 数组中数字出现的次数 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/10 16:42
 **/
func singleNumbers(nums []int) []int {
	var ret = 0
	for _, num := range nums {
		ret ^= num
	}
	var div = 1
	for div&ret == 0 {
		div <<= 1
	}
	var a int
	var b int
	for _, num := range nums {
		if div&num != 0 {
			a ^= num
		} else {
			b ^= num
		}
	}
	return []int{a, b}
}

/**
 * @Description: 剑指 Offer 34. 二叉树中和为某一值的路径 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/11 7:34
 **/
func pathSum34(root *TreeNode, target int) [][]int {
	var ans [][]int
	path := []int{}
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, curTarget int) {
		if node == nil {
			return
		}
		curTarget -= node.Val
		path = append(path, node.Val)
		if node.Left == nil && node.Right == nil && curTarget == 0 {
			var tmp = make([]int, len(path))
			copy(tmp, path)
			ans = append(ans, tmp)
		}
		dfs(node.Left, curTarget)
		dfs(node.Right, curTarget)
		path = path[:len(path)-1]
	}
	dfs(root, target)
	return ans
}

/**
 * @Description: 剑指 Offer 56 - II. 数组中数字出现的次数 II 中等
 * @Keyword: 异或
 * @Author: kami
 * @Date: 2022/7/11 8:27
 **/
func singleNumber56(nums []int) int {
	var k = make([]int, 32)
	for i := 0; i < len(nums); i++ {
		for j := 0; j < 32; j++ {
			var plus = nums[i] >> j & 1
			if plus == 1 {
				k[j] += 1
			}
		}
	}
	var res int
	for i := 31; i >= 0; i-- {
		res <<= 1
		if k[i]%3 == 1 {
			res |= 1
		}
	}
	return res
}

/**剑指 Offer 45. 把数组排成最小的数 中等
 * @Description:
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/11 9:00
 **/
func minNumber(nums []int) string {
	//将整数数组按字符串形式排序
	sort.Slice(nums, func(i, j int) bool {
		x := fmt.Sprintf("%d%d", nums[i], nums[j])
		y := fmt.Sprintf("%d%d", nums[j], nums[i])
		return x < y
	})

	res := ""
	for i := 0; i < len(nums); i++ {
		res += fmt.Sprintf("%d", nums[i])
	}
	return res
}

/**
 * @Description: 剑指 Offer 46. 把数字翻译成字符串 中等
 * @Keyword: 递归，最后两位取余判断
 * @Author: kami
 * @Date: 2022/7/11 15:05
 **/
func translateNum(num int) int {
	if num <= 9 {
		return 1
	}
	// 最后两位
	var ba = num % 100
	// 只能组成一个个数字，06,62
	if ba <= 9 || ba >= 26 {
		return translateNum(num / 10)
	}
	return translateNum(num/10) + translateNum(num/100)
}

/**
 * @Description: 剑指 Offer 46. 把数字翻译成字符串 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/11 15:05
 **/
func translateNum46(num int) int {
	numStr := strconv.Itoa(num)
	size := len(numStr)
	var dp = make([]int, size+1)
	dp[0] = 1
	dp[1] = 1
	for i := 2; i <= size; i++ {
		if numStr[i-2] == '1' || (numStr[i-2] == '2' && numStr[i-2] <= '5') {
			dp[i] = dp[i-1] + dp[i-2]
		} else {
			dp[i] = dp[i-1]
		}
	}
	return dp[size]
}

/**
 * @Description: 剑指 Offer 47. 礼物的最大价值 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/7/12 9:29
 **/
func maxValue(grid [][]int) int {
	var dp = make([][]int, len(grid))
	for i := 0; i < len(grid); i++ {
		dp[i] = make([]int, len(grid[0]))
		copy(dp[i], grid[i])
	}
	for i := 1; i < len(grid[0]); i++ {
		dp[0][i] += dp[0][i-1]
	}
	for i := 1; i < len(grid); i++ {
		dp[i][0] += dp[i-1][0]
	}

	for i := 1; i < len(grid); i++ {
		for j := 1; j < len(grid[0]); j++ {
			var max = dp[i-1][j]
			if dp[i][j-1] > max {
				max = dp[i][j-1]
			}
			dp[i][j] += max
		}
	}
	return dp[len(grid)-1][len(grid[0])-1]
}

/**
 * @Description: 剑指 Offer 49. 丑数 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/12 9:40
 **/
func nthUglyNumber(n int) int {
	var ugly = make([]int, n)
	ugly[0] = 1
	var i int
	var j int
	var k int
	for idx := 1; idx < n; idx++ {
		var minI = ugly[i] * 2
		var minJ = ugly[j] * 3
		var minK = ugly[k] * 5
		var tmp = getMin(minI, minJ, minK)
		if tmp == minI {
			i++
		}
		if tmp == minJ {
			j++
		}
		if tmp == minK {
			k++
		}
		ugly[idx] = tmp
	}
	return ugly[n-1]
}

/**
 * @Description: 剑指 Offer 59 - II. 队列的最大值 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/12 11:10
 **/
type MaxQueue struct {
	q1  []int
	max []int
}

func Constructor59() MaxQueue {
	return MaxQueue{
		make([]int, 0),
		make([]int, 0),
	}
}

func (this *MaxQueue) Max_value() int {
	if len(this.max) == 0 {
		return -1
	}
	return this.max[0]
}

func (this *MaxQueue) Push_back(value int) {
	this.q1 = append(this.q1, value)
	for len(this.max) != 0 && value > this.max[len(this.max)-1] {
		this.max = this.max[:len(this.max)-1]
	}
	this.max = append(this.max, value)
}

func (this *MaxQueue) Pop_front() int {
	n := -1
	if len(this.q1) != 0 {
		n = this.q1[0]
		this.q1 = this.q1[1:]
		if this.max[0] == n {
			this.max = this.max[1:]
		}
	}
	return n
}

/**
 * @Description:v剑指 Offer 66. 构建乘积数组 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/12 14:36
 **/
func constructArr(a []int) []int {
	if len(a) < 2 {
		return a
	}
	var pre = make([]int, len(a))
	pre[0] = a[0]
	var post = make([]int, len(a))
	post[len(a)-1] = a[len(a)-1]
	for i := 1; i < len(a); i++ {
		pre[i] = pre[i-1] * a[i]
		post[len(a)-i-1] = post[len(a)-i] * a[len(a)-i-1]
	}
	var res = make([]int, len(a))
	res[0] = post[1]
	res[len(a)-1] = pre[len(a)-2]
	for i := 1; i < len(a)-1; i++ {
		res[i] = pre[i-1] * post[i+1]
	}
	return res
}

/**
 * @Description: 剑指 Offer 60. n个骰子的点数 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/12 15:09
 **/
func dicesProbability(n int) []float64 {
	var dp = make([]float64, 6)
	var prob = 1.0 / 6.0
	for i := 0; i < 6; i++ {
		dp[i] = prob
	}
	// dp[i] 点数为i的概率
	for i := 2; i <= n; i++ {
		// 由于 dp[i] 仅由 dp[i−1] 递推得出，为降低空间复杂度，只建立两个一维数组 dp , tmp 交替前进即可。
		// i个筛子组成的点数个数，比如3个筛子的，点数为16个 3点-18点
		var tmp = make([]float64, 5*i+1)
		//  //先拿i-1个骰子的点数之和数组的第j个值，它所影响的是i个骰子时的temp[j+k]的值
		for j := 0; j < len(dp); j++ {
			for k := 0; k < 6; k++ {
				tmp[j+k] += dp[j] / 6.0
			}
		}
		dp = tmp
	}
	return dp
}

/**
 * @Description:剑指 Offer 67. 把字符串转换成整数 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/12 16:03
 **/
func strToInt(str string) int {
	//前导空格
	i := 0
	for i < len(str) && str[i] == ' ' {
		i++
	}
	str = str[i:]

	ans := 0      //64位数来存储好比较
	flag := false //符号位

	for i, v := range str {
		if v >= '0' && v <= '9' {
			ans = ans*10 + int(v-'0')
		} else if v == '-' && i == 0 {
			flag = true
		} else if v == '+' && i == 0 {
		} else {
			break
		}

		if ans > math.MaxInt32 {
			if flag {
				return math.MinInt32
			}
			return math.MaxInt32
		}
	}
	if flag {
		return -ans
	}
	return ans
}

/**
 * @Description: 剑指 Offer 43. 1～n 整数中 1 出现的次数 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/12 16:28
 **/
func countDigitOne(n int) int {
	// "1"出现的次数 = sum ("1"在各个计数位上出现的次数)
	// 从个位开始向最高位统计
	// 3101592
	// 将数字拆分为[a...][cur][b...]
	// cur 为当前位
	var base, res int64 = 1, 0
	n64 := int64(n)
	for base <= n64 {
		// 计算 a..., cur, b...
		a := n64 / base / 10
		cur := (n64 / base) % 10
		b := n64 % base
		// 将当前位设为1，考察其他部分的变化范围
		if cur > 1 {
			// 一、cur > 1，
			//          [3101 ] 5 [92]
			// 变化范围：[0-3101] 1 [0-99]
			// 总个数：   (a+1)  *  base
			res += (a + 1) * base
		} else if cur == 1 {
			// 二、cur == 1，
			//             [310] 1 [592]
			// 1、变化范围 [0-309] 1 [0-999]
			//              a    *  base
			// 2、变化范围 [310]   1 [0-592]
			//               1   *   (b+1)
			// 总个数：a *base + (b + 1)
			res += a*base + b + 1

		} else {
			// 三、cur < 1，
			//           [31] 0 [1592]
			// 变化范围 [0-30] 1 [0-9999]
			// 总个数    a     *   base
			res += a * base
		}
		// 统计更高一位
		base *= 10
	}
	return int(res)
}

/**
 * @Description: 剑指 Offer 51. 数组中的逆序对 困难
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/13 10:24
 **/
func reversePairs(nums []int) int {
	var mergeSort func(nums []int) []int
	var merge func(left, right []int) []int
	var cnt int
	mergeSort = func(nums []int) []int {
		if len(nums) < 2 {
			return nums
		}
		var mid = len(nums) / 2
		var left = make([]int, mid)
		copy(left, nums[0:mid])
		var right = make([]int, len(nums)-mid)
		copy(right, nums[mid:])
		return merge(mergeSort(left), mergeSort(right))
	}
	merge = func(left, right []int) []int {
		if len(left) <= 0 {
			return right
		}
		if len(right) <= 0 {
			return left
		}
		var res []int
		var leftIdx int
		var rightIdx int
		for leftIdx < len(left) || rightIdx < len(right) {
			if leftIdx < len(left) && rightIdx < len(right) {
				if left[leftIdx] <= right[rightIdx] {
					res = append(res, left[leftIdx])
					leftIdx++
				} else {
					res = append(res, right[rightIdx])
					rightIdx++
					cnt += len(left) - leftIdx
				}
			} else if leftIdx < len(left) {
				res = append(res, left[leftIdx])
				leftIdx++
			} else {
				res = append(res, right[rightIdx])
				rightIdx++
			}
		}
		return res
	}
	mergeSort(nums)

	return cnt
}

/**
 * @Description: 剑指 Offer 41. 数据流中的中位数
 * @Keyword:
 * @Author: kami
 * @Date: 2022/7/14 12:32
 **/
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

type MedianFinder struct {
	large, small *IntHeap
}

/** initialize your data structure here. */
func Constructor41() MedianFinder {
	a := &IntHeap{}
	b := &IntHeap{}
	heap.Init(a)
	heap.Init(b)

	return MedianFinder{a, b}

}

func (this *MedianFinder) AddNum(num int) {
	if this.large.Len() == 0 || num > (*this.large)[0] {
		heap.Push(this.large, num)
	} else {
		heap.Push(this.small, -num)
	}

	// 调节大小栈，确保 `FindMedian()` 得到正确的结果
	if this.large.Len() > this.small.Len()+1 {
		heap.Push(this.small, -heap.Pop(this.large).(int))
	} else if this.small.Len() > this.large.Len()+1 {
		heap.Push(this.large, -heap.Pop(this.small).(int))
	}
}

func (this *MedianFinder) FindMedian() float64 {
	if this.large.Len() < this.small.Len() {
		return float64(-(*this.small)[0])
	} else if this.large.Len() > this.small.Len() {
		return float64((*this.large)[0])
	}

	return float64(-(*this.small)[0]+(*this.large)[0]) / 2
}
